Search for: All records

We present a learning-based approach to prove infeasibility of kinematic motion planning problems. Sampling-based motion planners are effective in high-dimensional spaces but are only probabilistically complete. Consequently, these planners cannot provide a definite answer if no plan exists, which is important for high-level scenarios, such as task-motion planning. We propose a combination of bidirectional sampling-based planning (such as RRT-connect) and machine learning to construct an infeasibility proof alongside the two search trees. An infeasibility proof is a closed manifold in the obstacle region of the configuration space that separates the start and goal into disconnected components of the free configuration space. We train the manifold using common machine learning techniques and then triangulate the manifold into a polytope to prove containment in the obstacle region. Under assumptions about learning hyper-parameters and robustness of configuration space optimization, the output is either an infeasibility proof or a motion plan. We demonstrate proof construction for 3-DOF and 4-DOF manipulators and show improvement over a previous algorithm. 

The line coverage problem is the task of servicing a given set of one-dimensional features in an environment. Its applications include the inspection of road networks, power lines, and oil and gas lines. The line coverage problem is a generalization of the standard arc routing problems, and is NP-hard in general. We address the single robot line coverage problem where the service and deadhead costs are distinct and asymmetric. We model the problem as an optimization problem that minimizes the total cost of travel on a given graph. We present approximation algorithms to obtain bounded solutions efficiently, using the minimum cost flow problem. We build the main algorithm in stages by considering three simpler subproblems. The subproblems are based on the structure of the required graph, i.e., the graph induced by the features that require servicing. We fi rst present an optimal algorithm for the case of Eulerian graphs with only required edges. Next we consider general graphs, not necessarily Eulerian, with only required edges and present a 2-approximation algorithm. Finally, we consider the general case with both required and non-required edges. The approximation algorithm is dependent on the Asymmetric Traveling Salesperson Problem (ATSP), and is bounded by alpha(C) + 2, where alpha(C) is the approximation factor of the ATSP algorithm with C connected components. Our upper bound is also an improvement over the existing results for the asymmetric rural postman problem.